home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_05 / 1105105a < prev    next >
Encoding:
Text File  |  1993-03-07  |  2.9 KB  |  117 lines
  1. /* esort: Sort large files by merging subfiles */
  2.  
  3. #include <stdio.h>
  4. #include <assert.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. #define MAXLINES 1000
  9. #define MAXSUBFILES 15
  10.  
  11. struct subfile
  12. {
  13.     FILE *f;
  14.     char line[BUFSIZ];
  15. };
  16.  
  17. int comp(const void *, const void *);
  18. void make_subfile(char *[], size_t,
  19.   struct subfile *, size_t);
  20.  
  21. main()
  22. {
  23.     int i, merge_flag = 0;
  24.     size_t nlines, nfiles = 0, min_idx;
  25.     static char s[BUFSIZ], *lines[MAXLINES];
  26.     static struct subfile subfiles[MAXSUBFILES];
  27.  
  28.     /* Read file - form subfiles if needed */
  29.     for (nlines = 0; fgets(s,BUFSIZ,stdin); ++nlines)
  30.     {
  31.         if (nlines == MAXLINES ||
  32.           (lines[nlines] = malloc(strlen(s)+1)) == NULL)
  33.         {
  34.             /* Sort lines to a temporary merge file */
  35.             merge_flag = 1;  
  36.             make_subfile(lines,nlines,subfiles,nfiles++);
  37.             lines[nlines = 0] = malloc(strlen(s)+1);
  38.             assert(lines[0] != NULL);
  39.         }
  40.         strcpy(lines[nlines],s);
  41.     }
  42.  
  43.     if (merge_flag)
  44.     {
  45.         /* Form last merge file from remaining lines */
  46.         make_subfile(lines,nlines,subfiles,nfiles++);
  47.  
  48.         /* Prepare to read temporary files */
  49.         for (i = 0; i < nfiles; ++i)
  50.         {
  51.             FILE *f = subfiles[i].f;
  52.             rewind(f);
  53.             fgets(subfiles[i].line,BUFSIZ,f);
  54.         }
  55.  
  56.         /* Do the merge */
  57.         while (nfiles)
  58.         {
  59.             struct subfile *sfp;
  60.  
  61.             /* Find next output line */
  62.             for (min_idx = 0, i = 1; i < nfiles; ++i)
  63.                 if (strcmp(subfiles[i].line,
  64.                            subfiles[min_idx].line) < 0)
  65.                     min_idx = i;
  66.             sfp = &subfiles[min_idx];
  67.  
  68.             /* Output the line */
  69.             fputs(sfp->line,stdout);
  70.             fflush(stdout);
  71.             assert(!ferror(stdout));
  72.  
  73.             /* Get the next line from this file */
  74.             if (fgets(sfp->line,BUFSIZ,sfp->f) == NULL)
  75.                 subfiles[min_idx] = subfiles[--nfiles];
  76.         }
  77.     }
  78.     else
  79.     {
  80.         /* Sort singleton file */
  81.         qsort(lines,nlines,sizeof lines[0],comp);
  82.         for (i = 0; i < nlines; ++i)
  83.         {
  84.             fputs(lines[i],stdout);
  85.             fflush(stdout);
  86.             assert(!ferror(stdout));
  87.         }
  88.     }
  89.     
  90.     return 0;
  91. }
  92.  
  93. int comp(const void *p1, const void *p2)
  94. {
  95.     return strcmp(* (char **) p1, * (char **) p2);
  96. }
  97.  
  98. void make_subfile(char *lines[],size_t nl,
  99.                   struct subfile subf[],size_t nf)
  100. {
  101.     int i;
  102.     FILE *f = tmpfile();
  103.     assert(f);
  104.  
  105.     /* Write sorted subfile to temporary file */
  106.     qsort(lines,nl,sizeof lines[0],comp);
  107.     for (i = 0; i < nl; ++i)
  108.     {
  109.         fputs(lines[i],f);
  110.         fflush(f);
  111.         assert(!ferror(f));
  112.         free(lines[i]);
  113.     }
  114.     subf[nf].f = f;
  115. }
  116.  
  117.